//
//  124. 二叉树中的最大路径和.swift
//  Top600
//
//  Created by rjb on 2021/7/28.
//

import Foundation
class Solution124 {
    // 求最大路径和实际上是求左子树的最大路径和与右子树的路径和
    // 采用后序遍历,左，有，中
    var result: Int = Int.min
    func maxPathSum(_ root: TreeNode?) -> Int {
        caculateMaxPathSum(root)
        return result
    }
    @discardableResult
    func caculateMaxPathSum(_ root: TreeNode?) -> Int {
        guard let root = root else {
            return 0
        }
        let leftSum = caculateMaxPathSum(root.left) // 左边的最大和
        let rightSum = caculateMaxPathSum(root.right) // 右边的最大和
        // 当前节点的最大和有三种情况
        // 左 + 中
        // 右 + 中
        // 中
        let rootSum = max(leftSum + root.val, rightSum + root.val, root.val)
        // 最终的结果
        // result
        // 当前rootSum
        // 左 + 中 + 右
        result = max(result, rootSum, leftSum + rightSum + root.val)
        return rootSum
    }
    
    static func test() {
        let solution = Solution124()
        let node10 = TreeNode(-10)
        let node9 = TreeNode(9)
        let node20 = TreeNode(20)
        let node15 = TreeNode(15)
        let node7 = TreeNode(7)
        
        node10.left = node9
        node10.right = node20
        node20.left = node15
        node20.right = node7
        
        let result = solution.maxPathSum(node10)
        print(result)
    }
}
